class Solution(object):
    def sortString(self, s):
        P = [0] * 26
        for c in s:
            P[ord(c) - ord('a')] += 1
        e = max(P)
        t = ''
        for i in range(e):
            if i % 2 == 0:
                for j in range(26):
                    if P[j]:
                        t += chr(ord('a') + j)
                        P[j] -= 1
            else:
                for j in range(25, -1, -1):
                    if P[j]:
                        t += chr(ord('a') + j)
                        P[j] -= 1
        return t



data = Solution()
s = "aaaabbbbcccc"
print(data.sortString(s))
